Gemund, “Computing minimal diagnoses by greedy stochastic search

Most algorithms for computing diagnoses within a model-based diagnosis framework are deterministic. Such algo-rithms guarantee soundness and completeness, but are ΣP2-hard. To overcome this complexity problem, which pro-hibits the computation of high-cardinality diagnoses for large systems, we propose a novel approximation approach for multiple-fault diagnosis, based on a greedy stochastic al-gorithm called SAFARI (StochAstic Fault diagnosis Algo-RIthm). We prove that SAFARI can be configured to com-pute diagnoses which are of guaranteed minimality under subsumption. We analytically model SAFARI search as a Markov chain, and show a probabilistic bound on the min-imality of its minimal diagnosis approximations. We have applied this algorithm to the 74XXX and ISCAS85 suites of benchmark combinatorial circuits, demonstrating order-of-magnitude speedups over two state-of-the-art deterministic algorithms, CDA ∗ and HA∗, for multiple-fault diagnoses